package Deque;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

public class _Queue {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(new int[]{entry.getKey(),entry.getValue()});
            if (pq.size() > k) {
                pq.poll();
            }
        }
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = pq.poll()[0];
        }

          return res;

    }
    public void maxSlidingWindow() {
        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] res = new int[nums.length - k + 1];
        DefQueue defq = new DefQueue();
        //先初始化第一个窗口
        for (int i = 0; i < k; i++) {
            defq.push(nums[i]);
        }
        res[0] = defq.getMax();
        //开始
        for (int i = 1; i <= nums.length - k; i++) {
            defq.pop(nums[i - 1]);
            defq.push(nums[i + k - 1]);
            res[i] = defq.getMax();
        }
        for(int i : res){
            System.out.println(i);
        }


    }

    class DefQueue {
        Deque<Integer> q = new ArrayDeque<>();

        public void pop(int val) {
            if (!q.isEmpty() && q.peek() == val) {
                q.poll();
            }
        }

        public void push(int val) {
            while (!q.isEmpty() && q.getLast() < val) {
                q.pollLast();
            }
            q.offerLast(val);
        }

        public int getMax() {
            if (!q.isEmpty()) {
                return q.peek();
            }
            return -1;
        }
    }

}

class MyQueue {
    Deque<Integer> deq1 = new ArrayDeque<>();
    Deque<Integer> deq2 = new ArrayDeque<>();

    public MyQueue() {

    }

    public void push(int x) {
        deq1.push(x);
    }

    public int pop() {
        if (deq2.isEmpty()) {
            while (!deq1.isEmpty()) {
                deq2.push(deq1.pop());
            }
        }
        return deq2.pop();
    }

    public int peek() {
        if (deq2.isEmpty()) {
            while (!deq1.isEmpty()) {
                deq2.push(deq1.pop());
            }
        }
        if (deq2.isEmpty()) {
            return -1;
        }
        return deq2.peek();
    }

    public boolean empty() {
        if (deq1.isEmpty() && deq2.isEmpty()) {
            return true;
        }
        return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
